package com.lch.lru;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 刘晨辉
 * @date 2021/10/3 9:31 上午
 */
public class Lru {
    public static void main(String[] args) {
        Lru lru = new Lru(10);
        for (int i = 0; i < 12; i++) {
            lru.put(i,i);
        }
        Node node = lru.head;
        while (node.next != null) {
            System.out.println(node.getKey() + " ; " + node.getValue());
            node = node.next;
        }
    }

    class Node {
        private Node pre;
        private Node next;

        private int key;
        private int value;

        public int getKey() {
            return key;
        }

        public void setPre(Node pre) {
            this.pre = pre;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public Node getNext() {
            return next;
        }

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node(Node pre, Node next) {
            this.pre = pre;
            this.next = next;
        }
    }

    private int max;
    private int size;
    private Node head;
    private Node tail;
    private Map<Integer, Node> cache = new HashMap<>();

    Lru(int cap) {
        this.max = cap;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    boolean put(int key, int value) {
        Node node = cache.get(key);
        if (node== null) {
            node = new Node();
            node.setKey(key);
            node.setValue(value);
            cache.put(key, node);
            addToHead(node);
            ++size;
            if (size > max) {
                // 移除尾节点
                Node tailNode = removeTail();
                cache.remove(tailNode.getKey());
                --size;
            }
        } else {
            node.setValue(value);
            moveToHead(node);
        }
        return true;
    }

    int get(int key) {
        Node node = cache.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    private void addToHead(Node node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node res = tail.pre;
        removeNode(res);
        return res;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public Node getTail() {
        return tail;
    }

    public void setTail(Node tail) {
        this.tail = tail;
    }
}
